package problem42_Trapping_Rain_Water;
/**
 * （1）首先找到中间最高的柱子高度为maxHeight，然後從左向右疊加每一個i的蓄水量：首先求該i的左边最大值leftMax，然后maxHeight-leftMax.
 * （2）从右向左类似。
 * @author Ivan
 *
 */
public class Solution {
	public int trap(int[] height) {
		if(height.length==0||height.length==1||height.length==2) return 0;
		int maxHeightIndex=0;int water=0;
		for(int i=0;i<height.length;i++){
			maxHeightIndex=height[maxHeightIndex]>=height[i]?maxHeightIndex:i;
		}
		int maxLeftHeigth=height[0];
		for(int i=1;i<maxHeightIndex;i++){
			if(height[i]>maxLeftHeigth){
				maxLeftHeigth=height[i];
			}else{
				water+=maxLeftHeigth-height[i];
			}
		}
		int maxRightHeight=height[height.length-1];
		for(int i=height.length-2;i>maxHeightIndex;i--){
			if(height[i]>maxRightHeight){
				maxRightHeight=height[i];
			}else{
				water+=maxRightHeight-height[i];
			}
		}
		return water;
	}
}
